import random
from typing import *
from math import inf
from heapq import heapify, heappop, heappush, heapreplace


class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        m = len(nums)
        n = m // 3
        idx = [v for v in range(n, m)]
        idx.sort(key=lambda v: nums[v])
        a = 0
        b = sum(nums[idx[v]] for v in range(n))
        A, B = sum(nums[:n:]), sum(nums[n::])
        ql, qr = [], []
        for i in range(n):
            heappush(ql, -nums[i])
        mnin, mnout = set(), set()
        for i in range(n):
            heappush(qr, (-nums[idx[i]], idx[i]))
            mnin.add(idx[i])
        ans = inf
        for i in range(n, n + n):
            ans = min(ans, (A - B) - (a - b))
            A += nums[i]
            B -= nums[i]
            a -= heapreplace(ql, -nums[i])
            if i in mnin and i not in mnout:
                b -= nums[i]
                mnout.add(i)
            else:
                while qr and qr[0][1] in mnout:
                    heappop(qr)
                x, y = heappop(qr)
                b += x
                mnout.add(y)

        return min(ans, (A - B) - (a - b))


s = Solution()
# -5177
print(s.minimumDifference([3920, 5676, 3239, 2338, 949, 9805]))
print(3239 + 2338 - (949 + 9805))
# print(s.minimumDifference([3, 1, 2]) == -1)
# print(s.minimumDifference([7, 9, 5, 8, 1, 3]) == 1)

a = []
f = open("1.txt", "w")
for _ in range(10):
    for i in range(600):
        a.append(random.randint(1, 10000))
    print(a, file=f)
    a = []
